package xyz.scootaloo.oj.offer;

import org.junit.Test;

import java.lang.annotation.Target;

/**
 * @author flutterdash@qq.com
 * @since 2021/4/9 10:57
 */
public class P12 {

    private final int[][] position = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
    public boolean exist(char[][] board, String word) {
        int row = board.length;
        int column = board[0].length;
        boolean[][] tmp = new boolean[row][column];
        for (int r = 0; r<row; r++) {
            for (int c = 0; c<column; c++) {
                if (dfs(r, c, row, column, 1, word, board, tmp))
                    return true;
            }
        }
        return false;
    }

    private boolean dfs(int r, int c,
                        int row, int column,
                        int hasMatched, String target,
                        char[][] board, boolean[][] tmp) {
        if (r < 0 || r >= row || c < 0 || c >= column)
            return false;
        if (tmp[r][c] || board[r][c] != target.charAt(hasMatched - 1))
            return false;
        if (hasMatched == target.length())
            return true;
        tmp[r][c] = true;
        for (int[] pos : position) {
            if (dfs(r + pos[0], c + pos[1], row, column, hasMatched + 1, target, board, tmp))
                return true;
        }
        tmp[r][c] = false;
        return false;
    }

    @Test
    public void testFunc() {
        char[][] board = {
                {'A', 'B', 'C', 'E'},
                {'S', 'F', 'C', 'S'},
                {'A', 'D', 'E', 'E'}
        };
        System.out.println(exist(board, "ABCB"));
    }

}
